package tree;

public class Trie {

    Node root;

    public Trie(){

        root = new Node();
    }


    public void insert(String str){
        Node curNode = root;
        char[] chars = str.toCharArray();
        for(char ch:chars){
            if(!curNode.isContain(ch)){
                curNode.chars[ch-'a'] = ch;
            }
            Node nextNode = curNode.next;
            if(nextNode==null){
                nextNode = new Node();
                curNode.next = nextNode;
            }
            curNode = nextNode;
        }
        char lastChar = chars[chars.length-1];
        curNode.bytes[lastChar-'a'] = 1;

    }

    public boolean startsWith(String str){
        Node curNode = root;
        char[] chars = str.toCharArray();
        for(char ch:chars){
            if(curNode==null||!curNode.isContain(ch)){
                return false;
            }else{
                curNode = curNode.next;
            }

        }
        return true;

    }


    public boolean search(String str){
        Node curNode = root;
        char[] chars = str.toCharArray();
        for(char ch:chars){
            if(curNode==null||!curNode.isContain(ch)){
                return false;
            }else{
                curNode = curNode.next;
            }

        }
        int lastChar = chars[chars.length-1];
        if(curNode.bytes[lastChar-'a']==1){
            return true;
        }else{
            return false;
        }

    }


    class Node{
        char[] chars = new char[26];
        byte[] bytes = new byte[26];

        Node next;

        public boolean isContain(char ch){
            for(char chElem:chars){
                if(chElem==ch){
                    return true;
                }
            }
            return false;
        }

        // boolean

    }

    public static void main(String[] args){
        // int a = 'a';
        // System.out.println('b'-a);
        Trie trie = new Trie();
        trie.insert("helloworld");
        trie.insert("hhhdd");
        System.out.println(trie.search("helloworld"));
        System.out.println(trie.search("hello"));
        System.out.println(trie.startsWith("hello"));
        trie.insert("hello");
        System.out.println(trie.search("hello"));

    }


}